package 剑指offer;

public class Offer49_JZ33 {
    public static int nthUglyNumber(int n) {
        int count = 0;
        for (int i=1; i<Integer.MAX_VALUE; i++) {
            if (isuglyNum(i)) {
                count += 1;
                if (count == n) {
                    return i;
                }
            }
        }
        return 0;
    }

    public static boolean isuglyNum(int n) {
        while (n % 2 == 0) {
            n = n / 2;
        }
        while (n % 3 == 0) {
            n = n / 3;
        }
        while (n % 5 == 0) {
            n = n / 5;
        }
        return n == 1;
    }

    public static int nthUglyNumber2(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int a = 0, b = 0, c = 0;
        for(int i=1; i<n; i++) {
            int n2 = dp[a] * 2;
            int n3 = dp[b] * 3;
            int n4 = dp[c] * 5;
            dp[i] = Math.min(Math.min(n2, n3), n4);
            if (dp[i] == n2) {
                a++;
            }
            if (dp[i] == n3) {
                b++;
            }
            if (dp[i] == n4) {
                c++;
            }
        }
        return dp[n-1];
    }

    public static void main(String[] args) {
        System.out.println(nthUglyNumber2(10));
    }
}
